Ada pelbagai versi tentang asal-usul nasi hayashi. Menurut salah satu cerita yang sering dikutip, ilham masakan ini berasal dari pengusaha kilang Maruzen, Yūteki Hayashi. Menurut cerita lain, tukang masak bernama Hayashi di restoran Ueno Seiyoken sering menyediakan nasi hayashi untuk pekerja dapur dan pelayan ketika waktu makan. Kemungkinan lain, istilah "hayashi" berasal daripada sebutan orang Jepun sewaktu menyebut menu "hashed beef with rice".

Buku sejarah seratus tahun Maruzen (Maruzen Hyakunen-shi) menjelaskan bahawa pengarahnya, Yūteki Hayashi sering menghidangkan nasi dengan kuah pekat dari bermacam-macam sayuran yang digaul untuk para tetamu. Masakan tersebut disebut para tamu sebagai nasi Hayashi. Setelah itu, pelbagai restoran mengikut cara menghidangkan nasi hayashi. Buku yang sama menjelaskan bahawa ketika zaman Meiji, sudah wujud restoran ala Barat yang terkenal dengan hidangan nasi bersama hash beef. Rumah makan tersebut bernama Mikawa-ya di Kandasakuma-chō, Tokyo. Walaupun begitu, Maruzen tetap mendakwa Yūteki Hayashi sebagai pencipta nasi hayashi, dan masih terus menjual produk sos nasi hayashi dalam tin.